package com.test.daily.leetcode.y2022.m06.day0613.v04;

/**
 * @descriptions:
 * @author: Tom
 * @date: 2022/6/13 下午 11:25
 * @version: 1.0
 */
public class Solution {
    public static int group(int[] arr){
        int N = arr.length;
        int sum = 0;
        for (int i = 0; i < N; i++) {
            sum += arr[i];
        }
        sum /= 2;
        return process(arr, sum, 0);
    }
    public static int process(int[] arr, int rest, int index){
        if(index == arr.length){
            return 0;
        }
        int p1 = process(arr, rest, index +1);
        int p2= 0;
        if(rest - arr[index] >= 0){
            p2 = arr[index] + process(arr, rest - arr[index], index + 1);
        }
        return Math.max(p1, p2);
    }
    public static int dp1(int[] arr){
        int sum = 0;
        int N = arr.length;
        for(int i = 0; i < N; i++){
            sum += arr[i];
        }
        sum /= 2;
        int[][] dp = new int[N+1][sum+1];
        dp[N][0] = 0;
        for (int index = 0; index < N ; index++) {
            for (int rest = 0; rest <= sum; rest++) {
                int ans = 0;
                int p1 = dp[index+1][rest];
                int p2 = 0;
                if(rest - arr[index] > 0){
                    p2 = arr[index] + dp[index+ 1][rest-arr[index]];
                }
                ans = Math.max(p1, p2);
                dp[index][rest] = ans;
            }
        }
        return dp[0][sum];
    }
}
